package microsfot.java;

import java.util.Stack;

import alogrithm.tree.Node;

public class BTreePrintPathBySum {
	Stack<Integer> stack=new Stack<Integer>();
	
	/**
	 * 采用非递归的方式计算，思路为
	 * 从根节点开始遍历一致走到底部，对每一个节点都判断是否已经满足了期望的条件
	 * 如果满足条件，则打印路径，否则将当前节点入栈保存
	 * 
	 * 如果走到底还没有找到满足的条件，则将节点从栈中弹出，并判断其右子节点是否满足条件
	 * 如果右子节点满足条件，则打印，否则继续从栈中弹出节点（当前节点的父节点）
	 * 继续判断父节点的右节点是否满足条件
	 * @param root
	 * @param expect
	 */
	public void printPathByNonCR(Node<Integer> root,int expect){
		//声明一个栈用于保存访问过的节点
		Stack<Node<Integer>> stack=new Stack<Node<Integer>>();
		
		Node<Integer> parent=null;
		//开始遍历栈
		do{
			//一路向前遍历根节点的左子节点
			while(root!=null){
				
				//判断是否满足条件
				expect=expect-root.getData();
				//如果找到了
				if(expect==0){
					parent=root;
					expect+=root.getData();
					System.out.println("found at node " +root);
				}
				//如果未找到，则继续遍历左孩子节点
				else if(expect>0){
					stack.push(root);
				}else{
					break;
				}
				if(root.getLeft()!=null){
					parent=root;
				}
				root=root.getLeft();
			}
			/**
			  10
			 /   \
			5     12
		   /  \    /
		  4    7  0 
			 */
			//如果左孩子节点遍历完成，仍然未找到符合条件的节点，则将节点出栈并判断其右孩子节点
			root=stack.pop();
			
			//如果右子节点不为空，则继续向右边遍历
			if(root.getRight()==null||root.getRight()==parent||root.getLeft()!=parent){
				 expect = expect + root.getData();  
				 parent=root;
				 root = null;  
			}else {
				stack.push(root);
				parent=root;
				root=root.getRight();
			}
			
		}while(!stack.isEmpty());
	}
	
	/**
	 * 采用递归的方式计算
	 * @param tree
	 * @param currentSum
	 * @param expectSum
	 */
	public void printPathByRs (Node<Integer> tree,int currentSum,int expectSum){
		
		if(tree==null){
			return;
		}
		
		currentSum+=tree.getData();
		stack.push(tree.getData());
		
		//找到了和相等的路径,就把路径从栈中打印出来
		if(tree.getLeft()==null && tree.getRight()==null && currentSum==expectSum){
			System.out.println("找到路径:");
			int index=0;
			while(index<stack.size()){
				System.out.printf("%d->", stack.get(index++));
			}
			System.out.println();
		}
		
		//如果未到达叶子节点,则及判断当前节点是否有左孩子
		if(tree.getLeft()!=null){
			printPathByRs(tree.getLeft(),currentSum,expectSum);
		}
		
		//如果有右孩子
		if(tree.getRight()!=null){
			printPathByRs(tree.getRight(),currentSum,expectSum);
		}
		
		//如果遍历完成还未找到合适的路径,则需要向父节点回朔
		currentSum-=tree.getData();
		if(!stack.isEmpty()){
			stack.pop();
		}
	}
	
	/**
	 * 10
	 /   \
	5     12
   /  \    /
  4    7  0  
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> root=new Node<Integer>(10);
		Node<Integer> l5=new Node<Integer>(5);
		Node<Integer> r12=new Node<Integer>(11);
		Node<Integer> l4=new Node<Integer>(4);
		Node<Integer> r7=new Node<Integer>(7);
		
		root.setLeft(l5);
		root.setRight(r12);
		
		l5.setLeft(l4);
		l5.setRight(r7);
		
		r12.setLeft(new Node<Integer>(1));
		r12.setRight(new Node<Integer>(null,new Node<Integer>(1),0));
		l4.setLeft(new Node<Integer>(3));
		BTreePrintPathBySum path=new BTreePrintPathBySum();
		path.printPathByRs(root, 0, 22);
		path.printPathByNonCR(root, 22);
	}
}
